One example of a message passing process used in decoding low-density parity-check (LDPC) encoded data is as follows:
STEP1: For each variable node vj, compute a hard decision {circumflex over (l)}j based on the channel information and the incoming messages from all the connected check nodes ci. If the decisions {circumflex over (L)}=({circumflex over (l)}0, {circumflex over (l)}1, . . . , {circumflex over (l)}n-1) satisfy all the check nodes or a preset maximum number of iterations is reached, stop here. Otherwise, go to STEP2.
STEP2 (V-Node update): For each variable node vj, compute an outgoing message to each connected check node ci based on the incoming messages from all the other connected check nodes ci′(i′≠i). Go to STEP3.
STEP3 (C-Node update): For each check node ci, compute the outgoing message to each connected variable node vj based on the incoming messages from all the other connected variable nodes vj′(j′≠j). Go to STEP1.
The above message passing technique uses flooding scheduling. That is, all variable nodes are processed in parallel in STEP2, then all check nodes are processed in parallel in STEP3, and so on.
Some message-passing techniques use sequential scheduling, such as Horizontal Shuffle Scheduling (HSS) and Vertical Shuffle Scheduling (VSS). One example of a message passing process using HSS is defined as follows:
All the check nodes are sequentially divided into K groups, for example 1, 2, . . . , K. Each group contains r1, r2, . . . , rK (check nodes, respectively, so that r1+r2+ . . . +rK=m.
STEP1 (C-Node update): For each check node ciεk (k is initialized to 0), compute the outgoing message to each connected variable node vj based on the incoming messages from all the other connected variable nodes vj′(j′≠j). Go to STEP2.
STEP2 (V-Node update): For each variable node vj connected to any check node ciεk, compute its outgoing message to each connected check node c, based on the incoming messages from all the other connected check nodes ci′(i′≠i).
STEP3: k=k+1. If k=K, go to STEP4; else go to STEP1.
STEP4: For each variable node vj, compute the hard decision {circumflex over (l)}j based on the channel information and the incoming messages from all the connected check nodes ci. If the decisions {circumflex over (L)}=({circumflex over (l)}0, {circumflex over (l)}1, . . . , {circumflex over (l)}n-1) satisfy all the check nodes or a preset maximum number of iterations is reached, stop. Otherwise, k=0 and go to STEP1.
It would be desirable to develop techniques that improve the performance of decoding distorted LDPC encoded data. For example, it would be desirable if the processing time and/or the number of iterations (e.g., associated with message passing) could be reduced.